//给定一个二叉树，检查它是否是镜像对称的。 
//
// 
//
// 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 
//
//     1
//   / \
//  2   2
// / \ / \
//3  4 4  3
// 
//
// 
//
// 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 
//
//     1
//   / \
//  2   2
//   \   \
//   3    3
// 
//
// 
//
// 进阶： 
//
// 你可以运用递归和迭代两种方法解决这个问题吗？ 
// Related Topics 树 深度优先搜索 广度优先搜索 
// 👍 931 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Java：对称二叉树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P101_SymmetricTree {
    public static void main(String[] args) {
        Solution solution = new P101_SymmetricTree().new Solution();
        // TODO 此处开始你的表演

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    ///**
    // * 递归
    // * 时间复杂度 O(n)
    // * 空间复杂度 O(n)
    // */
    //class Solution {
    //    public boolean isSymmetric(TreeNode root) {
    //        return isMirror(root, root);
    //    }
    //
    //    private boolean isMirror(TreeNode p, TreeNode q) {
    //        if(p == null && q == null) {
    //            return true;
    //        }
    //        if(p == null || q == null) {
    //            return false;
    //        }
    //        return p.val == q.val && isMirror(p.left, q.right) && isMirror(p.right, q.left);
    //    }
    //}

    /**
     * 迭代
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root != null) {
                TreeNode p,q;
                Deque<TreeNode> deque = new LinkedList<>();
                deque.add(root.left);
                deque.add(root.right);
                while (!deque.isEmpty()) {
                    p = deque.removeFirst();
                    q = deque.removeFirst();
                    // 继续循环
                    if (p == null && q == null) {
                        continue;
                    }
                    if (p == null || q == null) {
                        return false;
                    }
                    if (p.val != q.val) {
                        return false;
                    }
                    deque.add(p.left);
                    deque.add(q.right);
                    deque.add(p.right);
                    deque.add(q.left);
                }
            }
            return true;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

}
